﻿using System;
using System.Linq;
using Algoritmia.Utils;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.GeneralizedCoinChange.QuantityAndSizeModeling
{
    public class RecursiveDynamicCoinChanger : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;

        public RecursiveDynamicCoinChanger(IList<int> values, IList<double> weights = null)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0,_n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            Func<int, int, double> L = null;
            L = (q, n) =>
                    {
                        if (q == 0 && n == 0)
                        {
                            return 0;
                        }
                        if (q > 0 && n == 0)
                        {
                            return double.PositiveInfinity;
                        }
                        return Enumerable.Range(0, (q/_values[n - 1]) + 1).Min(
                                i => L(q - i*_values[n - 1], n - 1) + i*_weights[n - 1]);
                    };
            return L(Q, _n);
        }

        #endregion
    }
}
